Most image processing systems can be considered in part as a spatial transformation system. In two-dimensional (2D) image processing, an image is generated by assigning a “color” value to every pixel in the 2D output space according to that pixel's relationship to some input data (possibly 3D). Introducing a coordinate system on the input and output data spaces, this relationship is conveniently expressed as a spatial mapping. The spatial mapping may be implicit in the design of the image processing system (lens arrangement, etc.), or may be explicitly specified to obtain a certain effect. Image warping, a term referring to a mapping between 2D input and output images or spaces, is often applied to correct optical distortions and various artifacts, such as aberrations, that are common in image capture and image display devices. Other uses of image warping include special effects, animation, image stitching and general geometric transformations. In general, image warping need not be a spatial transformation, however, the emphasis here is on spatial mappings.
Many electronic image distortion or transformation algorithms are designed with the primary goal to simplify the hardware implementation. This objective often leads to restrictions on the complexity of the spatial transformation or unrealistic descriptions of the transformation. For example, a method often used in image warping is the two-pass method. Specific warping systems based on the two-pass method include the Ampex device detailed in U.S. Pat. No. 4,472,732 to Bennett et al. The method disclosed is well suited for hardware implementations of real-time image processing systems and decomposes a 2D map into a series of 1D maps, which require only 1D filtering or re-sampling. Re-sampling in 1D is much simpler than in 2D and allows high optimization of the hardware using various architectures. However, the two-pass method is prone to the bottleneck effect, i.e. large compression in intermediate image, leading to loss of data. In the extreme case, complete data loss can occur, e.g. where an area is compressed to a line. This effect restricts the type of geometric transformations that can be applied. Other problems with the two-pass method involve generating the intermediate pass data.
Various enhancements to the two-pass method have been attempted in order to resolve these issues, as discussed in U.S. Pat. No. 5,175,808 to Sayre and U.S. Pat. No. 5,204,944 to Wolberg et al., these methods are based on a pixel-by-pixel description (i.e. look-up tables). A pixel-by-pixel description requires large storage spaces and more importantly, does not allow simple means for additional data manipulations. Once an image is warped, a second transformation, say a zoom operation, may be needed. In a pixel-by-pixel description, the entire grid has to be re-generated for a zooming warp, which can be inefficient, especially if zooming is a feature that is regularly used.
Other algorithms for spatial transformations, not necessarily based on the two-pass method, are limited to certain mapping types, such as rotations, linear scaling, affine, and perspective transforms as described in U.S. Pat. No. 4,835,532 to Fant, U.S. Pat. No. 4,975,976 to Kimata et al., U.S. Pat. No. 5,808,623 to Hamburg, and U.S. Pat. No. 6,097,855 to Levien. Some prior art methods also tend to identify the mathematical coordinate spaces with the physical memory spaces, which means that in a hardware implementation the transformations are restricted by the organization of the memory structure. Furthermore, most warping algorithms do not provide a simple format for applying independent transformations to different parts of an image. Complicated mappings, such as a change in topology (e.g. from circular image to rectangular image), require independent mappings for different regions.
These limitations can be eliminated using 2D representations, i.e. single-pass, making use of 2D filtering. Examples of systems based on 2D representations include the video processor and display unit of U.S. Pat. No. 5,384,912 to Orginc et al. and the integrated circuit TMC2302A manufactured by Fairchild Semiconductor. However, these prior art methods are based on a restricted subset of 2D transformations, hence they cannot represent general 2D mappings. In particular, neither of these systems provides the means for applying independent transformations to different parts of a single image.